/*
 * (C) Copyright 2014-2018, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.monotone

import org.jheaps.AddressableHeap
import org.junit.Assert
import org.junit.Assert.assertEquals
import org.junit.Test
import java.io.*
import java.util.*
import kotlin.math.abs

class LongRadixAddressableHeapTest {
    @Test
    fun testBug2() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(0L, 100L)
        h.insert(0L)
        assertEquals(0L, h.findMin().key)
        assertEquals(0L, h.deleteMin().key)
        h.insert(15L)
        assertEquals(15L, h.findMin().key)
    }

    @Test
    fun testVerySmall() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(15, 100)

        h.insert(15L)
        h.insert(50L)
        h.insert(21L)
        h.insert(51L)
        h.insert(30L)
        h.insert(25L)
        h.insert(18L)

        Assert.assertEquals(7, h.size())
        assertEquals(15L, h.findMin().key)
        Assert.assertEquals(7, h.size())
        assertEquals(15L, h.deleteMin().key)
        Assert.assertEquals(6, h.size())
        assertEquals(18L, h.findMin().key)
        assertEquals(18L, h.deleteMin().key)
        assertEquals(21L, h.findMin().key)
        assertEquals(21L, h.deleteMin().key)
        assertEquals(25L, h.findMin().key)
        assertEquals(25L, h.deleteMin().key)
        assertEquals(30L, h.findMin().key)
        assertEquals(30L, h.deleteMin().key)
        assertEquals(50L, h.findMin().key)
        assertEquals(50L, h.deleteMin().key)
        assertEquals(51L, h.findMin().key)
        assertEquals(51L, h.deleteMin().key)
        Assert.assertEquals(h.size(), 0)
        Assert.assertTrue(h.isEmpty)
    }

    @Test
    fun test() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(0, SIZE.toLong())

        for (i in 0 until SIZE) {
            h.insert(i.toLong())
            //assertEquals(0L, h.findMin().key, 1e-9)
            Assert.assertFalse(h.isEmpty)
            Assert.assertEquals(h.size(), i + 1L)
        }

        for (i in SIZE - 1 downTo 0) {
            //assertEquals((SIZE - i - 1).toLong(), h.findMin().key, 1e-9)
            h.deleteMin()
        }
    }

    @Test
    fun testSortRandomSeed1() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(0, Long.MAX_VALUE)

        val generator = Random(1)

        h.insert(0L)
        for (i in 1 until SIZE) {
            val d = (abs(generator.nextLong().toDouble()) + 1).toLong()
            h.insert(d)
        }

        var prev: Long? = null
        var cur: Long
        while (!h.isEmpty) {
            cur = h.deleteMin().key
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur) <= 0)
            }
            prev = cur
        }
    }

    @Test
    fun testSortRandomSeed2() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(0, Long.MAX_VALUE)

        val generator = Random(2)

        h.insert(0L)
        for (i in 1 until SIZE) {
            val d = (abs(generator.nextLong().toDouble()) + 1).toLong()
            h.insert(d)
        }

        var prev: Long? = null
        var cur: Long
        while (!h.isEmpty) {
            cur = h.deleteMin().key
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur) <= 0)
            }
            prev = cur
        }
    }

    @Test
    fun testSameMinMax() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(1L, 1L)

        for (i in 0..14) {
            h.insert(1L)
        }

        Assert.assertEquals(15, h.size())
        for (i in 0..14) {
            assertEquals(1L, h.deleteMin().key)
        }
        Assert.assertEquals(0, h.size())
    }

    @Test
    fun testMaxDifference() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(0L, Long.MAX_VALUE)

        h.insert(0L)
        h.insert(Long.MAX_VALUE)

        Assert.assertEquals(2, h.size())
        assertEquals(0L, h.deleteMin().key)
        assertEquals(Long.MAX_VALUE, h.deleteMin().key)
        Assert.assertEquals(0, h.size())
    }

    @Test
    fun testDelete() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(0L, 15L)

        val array: Array<AddressableHeap.Handle<Long, Void>> = Array(15){i->h.insert(i.toLong())}
        /*array = arrayOfNulls<AddressableHeap.Handle<*, *>>(15)
        for (i in 0..14) {
            array[i] = h.insert(i.toLong())
        }*/

        array[5].delete()
        assertEquals(0, h.findMin().key)
        array[7].delete()
        assertEquals(0, h.findMin().key)
        array[0].delete()
        assertEquals(1, h.findMin().key)
        array[2].delete()
        assertEquals(1, h.findMin().key)
        array[1].delete()
        assertEquals(3, h.findMin().key)
        array[3].delete()
        assertEquals(4, h.findMin().key)
        array[9].delete()
        assertEquals(4, h.findMin().key)
        array[4].delete()
        assertEquals(6, h.findMin().key)
        array[8].delete()
        assertEquals(6, h.findMin().key)
        array[11].delete()
        assertEquals(6, h.findMin().key)
        array[6].delete()
        assertEquals(10, h.findMin().key)
        array[12].delete()
        assertEquals(10, h.findMin().key)
        array[10].delete()
        assertEquals(13, h.findMin().key)
        array[13].delete()
        assertEquals(14, h.findMin().key)
        array[14].delete()
        Assert.assertTrue(h.isEmpty)
    }

    @Test
    fun testDelete1() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(0L, 10L)

        val array: Array<AddressableHeap.Handle<Long, Void>> = Array(8){i->h.insert(i.toLong())}
       /* array = arrayOfNulls<AddressableHeap.Handle<*, *>>(8)
        for (i in 0..7) {
            array[i] = h.insert(i.toLong())
        }*/

        array[5].delete()
       /* assertEquals(0L, h.findMin().key, 1e-9)
        array[7].delete()
        assertEquals(0L, h.findMin().key, 1e-9)
        array[0].delete()
        assertEquals(1L, h.findMin().key, 1e-9)
        array[2].delete()
        assertEquals(1L, h.findMin().key, 1e-9)
        array[1].delete()
        assertEquals(3L, h.findMin().key, 1e-9)*/
    }

    @Test
    fun testAddDelete() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(0, SIZE.toLong())

        val array: Array<AddressableHeap.Handle<Long, Void>>  = Array(SIZE){i->h.insert(i.toLong())}
        /*array = arrayOfNulls<AddressableHeap.Handle<*, *>>(SIZE)
        for (i in 0 until SIZE) {
            array[i] = h.insert(i.toLong())
        }*/

        for (i in SIZE - 1 downTo 0) {
            array[i].delete()
            if (i > 0) {
                assertEquals(0, h.findMin().key)
            }
        }
        Assert.assertTrue(h.isEmpty)
    }

    @Test
    fun testClear() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(0, 15)

        for (i in 0..14) {
            h.insert(i.toLong())
        }

        h.clear()
        Assert.assertEquals(0L, h.size())
        Assert.assertTrue(h.isEmpty)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testDeleteTwice() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(0, 15)

        val array: Array<AddressableHeap.Handle<Long, Void>>  = Array(15){i->h.insert(i.toLong())}
        /*array = arrayOfNulls<AddressableHeap.Handle<*, *>>(15)
        for (i in 0..14) {
            array[i] = h.insert(i.toLong())
        }*/

        array[5].delete()
        assertEquals(0, h.findMin().key)
        array[7].delete()
        assertEquals(0, h.findMin().key)
        array[0].delete()
        assertEquals(1, h.findMin().key)
        array[2].delete()
        assertEquals(1, h.findMin().key)
        array[1].delete()
        assertEquals(3, h.findMin().key)
        array[3].delete()
        assertEquals(4, h.findMin().key)
        array[9].delete()
        assertEquals(4, h.findMin().key)
        array[4].delete()
        assertEquals(6, h.findMin().key)

        // again
        array[2].delete()
    }

    @Test
    fun testDeleteMinUpdate() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(0, Long.MAX_VALUE)
        h.insert(0L)
        h.insert(0L)
        h.insert(Long.MAX_VALUE)
        h.insert(Long.MAX_VALUE)
        h.insert(Long.MAX_VALUE)
        h.insert(Long.MAX_VALUE)
        h.deleteMin()
        h.deleteMin()
        assertEquals(Long.MAX_VALUE, h.findMin().key)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testDeleteMinDeleteTwice() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(0, 100)
        val e1 = h.insert(50L)
        h.insert(100L)
        h.deleteMin()
        e1.delete()
    }

    @Test(expected = IllegalArgumentException::class)
    fun testDeleteMinDeleteTwice1() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(99, 200)

        for (i in 100..199) {
            h.insert(i.toLong())
        }

        h.deleteMin().delete()
    }

    @Test(expected = IllegalArgumentException::class)
    fun testDeleteMinDecreaseKey() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(100, 200)

        for (i in 100..199) {
            h.insert(i.toLong())
        }
        h.deleteMin().decreaseKey(0L)
    }

    /*@Test(expected = IllegalArgumentException::class)
    fun testBadInsert() {
        val h: AddressableHeap<Long?, Void> = LongRadixAddressableHeap<Void>(0, 100)
        h.insert(null)
    }*/

    @Test(expected = IllegalArgumentException::class)
    fun testBadInsert1() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(0, 100)
        h.insert(200L)
    }

    @Test(expected = NoSuchElementException::class)
    fun testBadDeleteMin() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(0, 100)
        h.deleteMin()
    }

    @Test(expected = NoSuchElementException::class)
    fun testBadFindMin() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(0, 100)
        h.findMin()
    }

    @Test
    fun testComparator() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(0, 100)
        Assert.assertNull(h.comparator())
    }

    @Test
    fun testDecreaseKey() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(0, 200)

        h.insert(0L) // monotone

        val array: Array<AddressableHeap.Handle<Long, Void>> = Array(15){i->h.insert(i.toLong()+100)}
        /*array = arrayOfNulls<AddressableHeap.Handle<*, *>>(15)

        for (i in 0..14) {
            array[i] = h.insert(i.toLong() + 100)
        }*/

        array[5].decreaseKey(5L)
        array[1].decreaseKey(50L)
        array[10].decreaseKey(3L)
        array[0].decreaseKey(1L)
        array[5].delete()
        array[2].delete()
        array[11].delete()
        array[9].delete()

        assertEquals(0, h.deleteMin().key)
        assertEquals(1, h.deleteMin().key)
        assertEquals(3, h.deleteMin().key)
        assertEquals(50, h.deleteMin().key)
        assertEquals(103, h.deleteMin().key)
        assertEquals(104, h.deleteMin().key)

        array[14].decreaseKey(111L)
        array[13].decreaseKey(109L)

        assertEquals(106, h.deleteMin().key)
        assertEquals(107, h.deleteMin().key)
        assertEquals(108, h.deleteMin().key)
        assertEquals(109, h.deleteMin().key)
        assertEquals(111, h.deleteMin().key)
        assertEquals(112, h.deleteMin().key)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIncreaseKey() {
        val h: AddressableHeap<Long, Void> = LongRadixAddressableHeap(0, 200)

        val array: Array<AddressableHeap.Handle<Long, Void>> = Array(15){i->h.insert(i.toLong()+100)}
        /*array = arrayOfNulls<AddressableHeap.Handle<*, *>>(15)
        for (i in 0..14) {
            array[i] = h.insert(i.toLong() + 100)
        }*/

        assertEquals(100, h.findMin().key)
        array[5].decreaseKey(5L)
        assertEquals(5, h.findMin().key)
        array[1].decreaseKey(102L)
    }

    @Test
    @Throws(IOException::class, ClassNotFoundException::class)
    fun testSerializable() {
        var h = LongRadixAddressableHeap<Void?>(0, 15)

        for (i in 0..14) {
            h.insert(i.toLong())
        }

        // write
        val baos = ByteArrayOutputStream()
        val oos = ObjectOutputStream(baos)
        oos.writeObject(h)
        oos.close()
        val data = baos.toByteArray()

        // read
        val ois = ObjectInputStream(ByteArrayInputStream(data))
        val o = ois.readObject()
        ois.close()
        h = o as LongRadixAddressableHeap<Void?>

        for (i in 0..14L) {
            Assert.assertEquals((15 - i).toLong(), h.size())
            assertEquals(i, h.findMin().key)
            h.deleteMin()
        }
        Assert.assertTrue(h.isEmpty)
    }

    @Test
    fun testGetValue() {
        val h: AddressableHeap<Long, String> = LongRadixAddressableHeap(0, 0)
        assertEquals("hello", h.insert(0L, "hello").value)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIllegalConstruction() {
        LongRadixAddressableHeap<Void>(-1, 10)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIllegalConstruction1() {
        LongRadixAddressableHeap<Void>(10, 9)
    }

    companion object {
        private const val SIZE = 100000
    }
}
